package 力扣_树算法.遍历.根据遍历构建二叉树;


import java.util.HashMap;
import java.util.Map;

/**106. 从中序与后序遍历序列构造二叉树
 * @author zx
 * @create 2022-04-13 20:17
 */
public class Num106 {
    /**
     注意这里有需要先创建右子树,再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是
     先存储左子树的节点,再存储右子树的节点,最后存储根节点,如果按每次选择
     [后序遍历的最后一个节点]为根节点,则先被构造出来的应该为右子树。
     */
    // 后序遍历的数组最后一个元素代表的即为根节点
    private int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        return buildTreeByPostOrder(inorder,postorder,0,postorder.length - 1);

    }
    //在preOrder的[left...right]借助后序遍历还原二叉树,返回二叉树的根节点
    private TreeNode buildTreeByPostOrder(int[] inorder,int[] postorder,int left,int right){
        if(left > right){
            return null;
        }
        TreeNode root = new TreeNode(postorder[index]);
        index--;
        int pos = findIndex(inorder,root.val);
        //必须先右后左
        root.right = buildTreeByPostOrder(inorder,postorder,pos + 1,right);
        root.left = buildTreeByPostOrder(inorder,postorder,left,pos - 1);
        return root;
    }
    //找到给定值在中序遍历中的索引
    private int findIndex(int[]inorder,int val){
        for(int i = 0;i < inorder.length;i++){
            if(val == inorder[i]){
                return i;
            }
        }
        return -1;
    }


    // 后序遍历的数组最后一个元素代表的即为根节点
//    private int index;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTreeByPostOrder(postorder,0,postorder.length - 1);
    }
    //在preOrder的[left...right]借助后序遍历还原二叉树,返回二叉树的根节点
    private TreeNode buildTreeByPostOrder(int[] postorder, int left, int right){
        if(left > right){
            return null;
        }
        TreeNode root = new TreeNode(postorder[index]);
        index--;
        int pos = map.get(root.val);
        //必须先右后左
        root.right = buildTreeByPostOrder(postorder,pos + 1,right);
        root.left = buildTreeByPostOrder(postorder,left,pos - 1);
        return root;
    }
}
